Use of navigation assistance technology to help individuals get from one place to another is widespread. For instance, automobiles, mobile phones, and even wrist watches may include navigation functionality to provide maps, directions, and searches for points of interest (POIs). The navigation assistance technologies allow users to plan trips, obtain directions and even provide updates regarding a user's location while travelling. Navigation assistance technologies may also enable users to “search along a route” for POIs (e.g., gas, restaurant, park, hotel, grocery store, coffee, etc.) in connection with a planned route between start and end points. Traditionally, searches along a route begin with an already established route and then find POIs along a route based on search criteria. In this approach, a selected POI(s) is added as an intermediate stop in the established route by detouring away from and then back to the established route. In scenarios in which a user is searching for a particular type of location with multiple possible location options (e.g., Costco, hardware store, coffee shop) and does not prefer/designate a specific location, starting with the established route (e.g., computing the route first) may result in a less than optimal route. This inefficiency occurs because the pre-established route creates an additional constraint on the search and when the intermediate stop criteria are introduced, existing algorithms are not configured to deviate from the already established route and/or fail to consider whether an alternative overall route including the specified stop would be more efficient.